package com.example.design.leetcode.recursion;

//剑指 Offer 07. 重建二叉树
//    输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
//    假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
//
//    示例 1:
//        3
//       / \
//      9   20
//         /  \
//        15   7
//    Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//    Output: [3,9,20,null,null,15,7]
//
//    示例 2:
//    Input: preorder = [-1], inorder = [-1]
//    Output: [-1]
//
//    限制：
//    0 <= 节点个数 <= 5000
//
//    注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

//根据二叉树的遍历特点可知：
//    前序遍历首个元素为根节点；
//    在中序遍历中可由根节点位置将其分为‘左子树’‘根节点’‘右子树’；
//    在中序遍历中可知左右子树的节点数量。
//    因此可以确定三个节点关系，根据树的特点，我们很自然的可以使用递归方法。

// 不需要真的把 preorder 和 inorder 切分了，只需要用分别用两个指针指向开头和结束位置即可


public class Practice01 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        // preorder 为空，直接返回 null
        if (p_start == p_end) {
            return null;
        }

        // 构造根节点
        int root_val = preorder[p_start];
        TreeNode root = new TreeNode(root_val);

        //在中序遍历中找到根节点的位置
        int i_root_index = 0;
        for (int i = i_start; i < i_end; i++) {
            if (root_val == inorder[i]) {
                i_root_index = i;
                break;
            }
        }

        // 中序遍历中，根节点的左子树元素个数
        int leftNum = i_root_index - i_start;

        //递归的构造左子树
        // preorder前序遍历集合的左子树，p_start + 1左子树开始索引闭区间，左子树结束索引开区间，开始位置 + 左子树元素个数 + 1
        // inorder中序遍历集合的左子树，i_start左子树开始索引闭区间，左子树结束索引开区间，就是根节点索引i_root_index
        root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index);

        //递归的构造右子树
        // preorder前序遍历集合的右子树，p_start + leftNum + 1右子树开始索引闭区间，右子树结束索引开区间，p_end
        // inorder中序遍历集合的右子树，i_root_index + 1右子树开始索引闭区间，右子树结束索引开区间，i_end
        root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);

        return root;
    }

    private TreeNode buildTreeHelper1(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        if (p_start == p_end) {
            return null;
        }

        // 构造根节点
        TreeNode root = new TreeNode(preorder[p_start]);

        // 获取根节点在中序遍历中的索引
        int rootIndex = 0;
        for (int i = i_start; i < i_end; i++) {
            if (preorder[p_start] == inorder[i]) {
                rootIndex = i;
                break;
            }
        }

        // 左子树元素个数
        int leftNum = rootIndex - i_start;

        // 左子树
        root.left = buildTreeHelper1(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, rootIndex);
        // 右子树
        root.right = buildTreeHelper1(preorder, p_start + leftNum + 1, p_end, inorder, rootIndex + 1, i_end);
        return root;
    }

    public static void main(String[] args) {

        Practice01 practice01 = new Practice01();
        TreeNode treeNode = practice01.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(treeNode);
    }
}